home *** CD-ROM | disk | FTP | other *** search
/ X User Tools / X User Tools (O'Reilly and Associates)(1994).ISO / sources / libxpm / libxpm34.gz / libxpm34 / xpm-3.4 / lib / hashtable.c < prev    next >
C/C++ Source or Header  |  1994-03-14  |  5KB  |  209 lines
  1. /* Copyright 1989-94 GROUPE BULL -- See license conditions in file COPYRIGHT */
  2. /*****************************************************************************\
  3. * hashtable.c:                                                                *
  4. *                                                                             *
  5. *  XPM library                                                                *
  6. *                                                                             *
  7. *  Developed by Arnaud Le Hors                                                *
  8. *  this originaly comes from Colas Nahaboo as a part of Wool                  *
  9. *                                                                             *
  10. \*****************************************************************************/
  11.  
  12. #include "xpmP.h"
  13.  
  14. LFUNC(AtomMake, xpmHashAtom, (char *name, void *data));
  15. LFUNC(HashTableGrows, int, (xpmHashTable * table));
  16.  
  17. static xpmHashAtom
  18. AtomMake(name, data)            /* makes an atom */
  19.     char *name;                /* WARNING: is just pointed to */
  20.     void *data;
  21. {
  22.     xpmHashAtom object = (xpmHashAtom) XpmMalloc(sizeof(struct _xpmHashAtom));
  23.  
  24.     if (object) {
  25.     object->name = name;
  26.     object->data = data;
  27.     }
  28.     return object;
  29. }
  30.  
  31. /************************\
  32. *              *
  33. *  hash table routines      *
  34. *              *
  35. \************************/
  36.  
  37. /*
  38.  * Hash function definition:
  39.  * HASH_FUNCTION: hash function, hash = hashcode, hp = pointer on char,
  40.  *                 hash2 = temporary for hashcode.
  41.  * INITIAL_TABLE_SIZE in slots
  42.  * HASH_TABLE_GROWS how hash table grows.
  43.  */
  44.  
  45. /* Mock lisp function */
  46. #define HASH_FUNCTION       hash = (hash << 5) - hash + *hp++;
  47. /* #define INITIAL_HASH_SIZE 2017 */
  48. #define INITIAL_HASH_SIZE 256        /* should be enough for colors */
  49. #define HASH_TABLE_GROWS  size = size * 2;
  50.  
  51. /* aho-sethi-ullman's HPJ (sizes should be primes)*/
  52. #ifdef notdef
  53. #define HASH_FUNCTION    hash <<= 4; hash += *hp++; \
  54.     if(hash2 = hash & 0xf0000000) hash ^= (hash2 >> 24) ^ hash2;
  55. #define INITIAL_HASH_SIZE 4095        /* should be 2^n - 1 */
  56. #define HASH_TABLE_GROWS  size = size << 1 + 1;
  57. #endif
  58.  
  59. /* GNU emacs function */
  60. /*
  61. #define HASH_FUNCTION       hash = (hash << 3) + (hash >> 28) + *hp++;
  62. #define INITIAL_HASH_SIZE 2017
  63. #define HASH_TABLE_GROWS  size = size * 2;
  64. */
  65.  
  66. /* end of hash functions */
  67.  
  68. /*
  69.  * The hash table is used to store atoms via their NAME:
  70.  *
  71.  * NAME --hash--> ATOM |--name--> "foo"
  72.  *               |--data--> any value which has to be stored
  73.  *
  74.  */
  75.  
  76. /*
  77.  * xpmHashSlot gives the slot (pointer to xpmHashAtom) of a name
  78.  * (slot points to NULL if it is not defined)
  79.  *
  80.  */
  81.  
  82. xpmHashAtom *
  83. xpmHashSlot(table, s)
  84.     xpmHashTable *table;
  85.     char *s;
  86. {
  87.     xpmHashAtom *atomTable = table->atomTable;
  88.     unsigned int hash;
  89.     xpmHashAtom *p;
  90.     char *hp = s;
  91.     char *ns;
  92.  
  93.     hash = 0;
  94.     while (*hp) {            /* computes hash function */
  95.     HASH_FUNCTION
  96.     }
  97.     p = atomTable + hash % table->size;
  98.     while (*p) {
  99.     ns = (*p)->name;
  100.     if (ns[0] == s[0] && strcmp(ns, s) == 0)
  101.         break;
  102.     p--;
  103.     if (p < atomTable)
  104.         p = atomTable + table->size - 1;
  105.     }
  106.     return p;
  107. }
  108.  
  109. static int
  110. HashTableGrows(table)
  111.     xpmHashTable *table;
  112. {
  113.     xpmHashAtom *atomTable = table->atomTable;
  114.     int size = table->size;
  115.     xpmHashAtom *t, *p;
  116.     int i;
  117.     int oldSize = size;
  118.  
  119.     t = atomTable;
  120.     HASH_TABLE_GROWS
  121.     table->size = size;
  122.     table->limit = size / 3;
  123.     atomTable = (xpmHashAtom *) XpmMalloc(size * sizeof(*atomTable));
  124.     if (!atomTable)
  125.     return (XpmNoMemory);
  126.     table->atomTable = atomTable;
  127.     for (p = atomTable + size; p > atomTable;)
  128.     *--p = NULL;
  129.     for (i = 0, p = t; i < oldSize; i++, p++)
  130.     if (*p) {
  131.         xpmHashAtom *ps = xpmHashSlot(table, (*p)->name);
  132.  
  133.         *ps = *p;
  134.     }
  135.     XpmFree(t);
  136.     return (XpmSuccess);
  137. }
  138.  
  139. /*
  140.  * xpmHashIntern(table, name, data)
  141.  * an xpmHashAtom is created if name doesn't exist, with the given data.
  142.  */
  143.  
  144. int
  145. xpmHashIntern(table, tag, data)
  146.     xpmHashTable *table;
  147.     char *tag;
  148.     void *data;
  149. {
  150.     xpmHashAtom *slot;
  151.  
  152.     if (!*(slot = xpmHashSlot(table, tag))) {
  153.     /* undefined, make a new atom with the given data */
  154.     if (!(*slot = AtomMake(tag, data)))
  155.         return (XpmNoMemory);
  156.     if (table->used >= table->limit) {
  157.         int ErrorStatus;
  158.  
  159.         if ((ErrorStatus = HashTableGrows(table)) != XpmSuccess)
  160.         return (ErrorStatus);
  161.         table->used++;
  162.         return (XpmSuccess);
  163.     }
  164.     table->used++;
  165.     }
  166.     return (XpmSuccess);
  167. }
  168.  
  169. /*
  170.  *  must be called before allocating any atom
  171.  */
  172.  
  173. int
  174. xpmHashTableInit(table)
  175.     xpmHashTable *table;
  176. {
  177.     xpmHashAtom *p;
  178.     xpmHashAtom *atomTable;
  179.  
  180.     table->size = INITIAL_HASH_SIZE;
  181.     table->limit = table->size / 3;
  182.     table->used = 0;
  183.     atomTable = (xpmHashAtom *) XpmMalloc(table->size * sizeof(*atomTable));
  184.     if (!atomTable)
  185.     return (XpmNoMemory);
  186.     for (p = atomTable + table->size; p > atomTable;)
  187.     *--p = NULL;
  188.     table->atomTable = atomTable;
  189.     return (XpmSuccess);
  190. }
  191.  
  192. /*
  193.  *   frees a hashtable and all the stored atoms
  194.  */
  195.  
  196. void
  197. xpmHashTableFree(table)
  198.     xpmHashTable *table;
  199. {
  200.     xpmHashAtom *p;
  201.     xpmHashAtom *atomTable = table->atomTable;
  202.  
  203.     for (p = atomTable + table->size; p > atomTable;)
  204.     if (*--p)
  205.         XpmFree(*p);
  206.     XpmFree(atomTable);
  207.     table->atomTable = NULL;
  208. }
  209.